package LeetCode.interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题

　　Given a binary tree, find its minimum depth. 
　　The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 

题目大意

　　给定一棵两叉树求树的最小深度。 (求：根节点到最近的叶子节点 )

解题思路
	@_104_Maximum_Depth_of_Binary_Tree 的逆问题
结题思路：和找最大距离不同之处在于：找最小距离要注意Math.min(minDepth(node.left), minDepth(node.right)) + 1的区别应用，
	因为可能存在左右子树为空的情况，此时值就为0，但显然值是不为0的（只有当二叉树为空才为0），所以，在这里注意一下即可！

 * @Date 2017-09-14 00：09
 */
public class _111_Minimum_Depth_of_Binary_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	/***
	 * TODO：需要仔细思考下
	 * @param node
	 * @return
	 */
	public int minDepth(TreeNode node) {
        if (node == null)   return 0;
        else if (node.left==null && node.right==null)    return 1;
        else {
        	/***
        	 * 注：不能if (node.left !=null)	return minDepth(node.left)+1;
        	 * 		原因：存在情况left和right都不为空(第54行), 此时可能right的深度比left小
        	 */
        	if (node.left ==null)	return minDepth(node.right)+1;
        	if (node.right==null)	return minDepth(node.left)+1;
        	return Math.min(minDepth(node.left), minDepth(node.right)) + 1;
        }
    }

	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	private TreeNode newTree1() {
		return new TreeNode(1, 
					null, null
				);
	}
	
	
	//中序遍历：看下结果
    public void traverse (TreeNode rs) {
    	if (rs == null)	return;
    	traverse(rs.left);
    	LogUtils.print(rs.val);
    	traverse(rs.right);
    }
	
	
	public static void main(String[] args) {
		_111_Minimum_Depth_of_Binary_Tree obj = new _111_Minimum_Depth_of_Binary_Tree();
		LogUtils.println("结果", 
				obj.minDepth(
						obj.newTree1()
				));
	}
}
